package org.nix.utils.dijkstra;

import org.nix.entity.City;
import org.nix.entity.CityDistance;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Create by zhangpe0312@qq.com on 2018/4/19.
 */
public class MyDijkstra {

    // 最短路径
    private Queue<City> ways = new LinkedList<>();

    // 路径长度
    private double length;


    /**
     * 计算出开始城市到目的城市的距离
     *
     * @param cities 全部城市信息
     * @param start  起始城市
     * @param end    终止城市
     * @return 返回最短路径长度
     */
    public void dijkstraDistance(List<City> cities, City start, City end) {

        // 获取城市节点数目
        int n = cities.size();

        // 开始城市在list里面的坐标
        int startIndex = cities.indexOf(start);

        // 目的城市在list里面的坐标
        int endIndex = cities.indexOf(end);

        // 标记当前城市的最短路径是否已经求出 1表示已经求出， java默认基本类型int为0
        int[] visited = new int[n];

        // 记录起始城市到其他城市的最短路径
        double[] shortPath = new double[n];

        // 记录起始城市到其他城市的路径
        Ways[] initPath = initPath(start,cities);

        // 当前城市到其他城市的距离集合
        List<CityDistance> startCityDistances = cities.get(startIndex).getToCityDistance();

        visited[startIndex] = 1;

        for (int i = 1; i < n; i++) {

            int k = -1;
            double dmin = Integer.MAX_VALUE;

            for (int j = 0; j < n; j++) {
                double dis = startCityDistances.get(j).getDistance();
                if (i == 3){
                    System.out.print("");
                }
                if (visited[j] == 0 &&
                        dis < dmin) {
                    dmin = dis;
                    k = j;
                }
            }

            shortPath[k] = dmin;
            visited[k] = 1;

            for (int j = 0; j < n; j++) {

                // 如果 开始城市到达第K个城市的距离 + 第K个城市到第J个城市的距离 小于 开始城市直接到达目的城市的距离
                double dis = startCityDistances.get(k).getDistance() +
                        cities.get(k).getToCityDistance().get(j).getDistance();


                if (visited[j] == 0 && dis < startCityDistances.get(j).getDistance()) {

                    startCityDistances.get(j).setDistance(dis);

                    Ways ways = new Ways();
                    ways.setRoot(initPath[k].getRoot());
                    Queue<City> queue = new LinkedList<>();
                    Queue<City> kQueue = initPath[k].getNext();

                    for (City city :kQueue) {
                        queue.offer(city);
                    }
                    ways.setNext(queue);
                    ways.getNext().offer(cities.get(j));

                    initPath[j]=ways;

                }
            }
        }

//        System.out.print("从"+start.getCityName()+"到"+end.getCityName()+
//        "的路径为:\n");
        Ways ways = initPath[endIndex];
        addWay(ways.getRoot());
//        System.out.print(ways.getRoot().getCityName() + " ");
        Queue<City> queue = ways.getNext();
        for (City city : queue) {
            addWay(city);
//            System.out.print(city.getCityName() + " ");
        }
//
//        System.out.println();
//
//        System.out.println("从"+start.getCityName()+"到"+end.getCityName()+
//                "的距离为:" + shortPath[endIndex]);
//
//        System.out.println();

        length = shortPath[endIndex];
    }

    private  Ways[] initPath(City start , List<City> cities){

        int n = cities.size();

        Ways[] ways = new Ways[n];
        for (int i = 0; i <n ; i++) {
            Queue<City> queue = new LinkedList<>();
            queue.offer(cities.get(i));
            ways[i] = new Ways(start,queue);
        }

        return ways;
    }

    public Queue<City> getWays() {
        return ways;
    }

    private void addWay(City city) {
       ways.offer(city);
    }

    public double getLength() {
        return length;
    }

    public void setLength(double length) {
        this.length = length;
    }
}

/**
 * 展示路径
 */
class Ways{

    private City root;
    private Queue<City> next;

    public Ways() {
    }

    public Ways(City root, Queue<City> next) {
        this.root = root;
        this.next = next;
    }

    public Ways(City root) {
        this.root = root;
    }

    public City getRoot() {
        return root;
    }

    public void setRoot(City root) {
        this.root = root;
    }

    public Queue<City> getNext() {
        return next;
    }

    public void setNext(Queue<City> next) {
        this.next = next;
    }
}
